package com.rui.study.algorithm.P_股票_买卖股票最佳时机Ⅲ_最多两笔交易;

import java.util.Arrays;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-07 09:09
 **/
public class Solution2前一次寻找出售点后一次寻找购入点 {

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        int[] before = new int[n];
        int[] after = new int[n];
        int maxProfit = 0;

        int min = prices[0];
        for (int i = 1; i < n; i++) {
            min = Math.min(min, prices[i]);
            if (prices[i] - min > maxProfit) maxProfit = prices[i] - min;
            before[i] = maxProfit;
        }
        System.out.println(Arrays.toString(before));

        maxProfit = 0;
        int max = prices[n-1];
        for (int i = n-2; i >= 0; i--) {
            max = Math.max(max, prices[i]);
            after[i] = max - prices[i];
            if (max - prices[i] > maxProfit) maxProfit = max - prices[i];
            after[i] = maxProfit;
        }
        System.out.println(Arrays.toString(after));


        maxProfit = 0;
        for (int i = 0; i < n; i++) {
            maxProfit = Math.max(maxProfit, before[i] + after[i]);
        }

        return maxProfit;
    }

    public static void main(String[] args) {
//        int[] prices = {3,2,6,5,0,3};
//        int[] prices = {3,2,6,5,0,3,2,6};
//        int[] prices = {1,4,2,7};
        int[] prices = {1,2,4,2,5,7,2,4,9,0};
//        int[] prices = {48,12,60,93,97,42,25,64,17,56,85,93,9,48,52,42,58,85,81,84,69,36,1,54,23,15,72,15,11,94};
//        int[] prices = {48,12,60,93,97,42,25,64,17,56,85,93,9,48,52,42,58,85};
        Solution2前一次寻找出售点后一次寻找购入点 solution = new Solution2前一次寻找出售点后一次寻找购入点();
        long start = System.currentTimeMillis();
        int maxProfit = solution.maxProfit(prices);
        long end = System.currentTimeMillis();
        System.out.println("最大收益：" + maxProfit + ", 耗时：[" + (end - start) + "ms]");
    }

}
